package stackAndQueue

import "strconv"

/*
时间复杂度：O(N)
空间复杂度:O(1)
单调栈
*/
func maximumSwap(num int) int {
	stack := make([]int, 0)
	bs := []byte(strconv.Itoa(num))
	for i, _ := range bs {
		for len(stack) > 0 && bs[i] >= bs[stack[len(stack)-1]] {
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, i)
	}
	for i, v := range stack {
		if i != v {
			bs[i], bs[v] = bs[v], bs[i]
		}
	}
	result, _ := strconv.Atoi(string(bs))
	return result
}
